package www.study.com;

//两两交换链表中的节点 https://leetcode.cn/problems/swap-nodes-in-pairs/
public class code23 {
    public static void main(String[] args) {

    }

     public class ListNode {
         int val;
         ListNode next;
         ListNode() {}
         ListNode(int val) { this.val = val; }
         ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     }
    class Solution {
        /**
         * 这个函数可以看成返回nowPos两两替换后的头节点信息，因此可以有如下递归
         * @param nowPos
         * @return
         */
        public ListNode swapPairs(ListNode nowPos) {
            //方式二：递归
            if (nowPos == null || nowPos.next == null) {
                return nowPos;
            }
            //新节点复制，防止之后的修改被覆盖掉
            ListNode headNext = nowPos.next;
            //修改nowPos.next的信息
            nowPos.next = swapPairs(headNext.next);
            //修改headNext信息，完成替换功能
            headNext.next = nowPos;
            return headNext;
        }
        //方式一
        /*public ListNode swapPairs(ListNode head) {
            if(head == null || head.next == null) return head;
            ListNode lef = head;
            ListNode rig = head.next;
            ListNode res = null; //头节点
            ListNode pre = null;
            while(lef != null && rig != null){
                ListNode lefNext = rig.next;
                ListNode rigNext = rig.next != null ? rig.next.next : null;
                lef.next = rig.next;
                rig.next = lef;
                if(res == null){
                    res = rig;
                }else{
                    pre.next = rig;
                }
                pre = lef;
                lef = lefNext;
                rig = rigNext;
            }
            return res;
        }*/
    }
}
